package com.gitee.wsl.doc.prosemirror.history.ropesequence

import kotlin.math.max
import kotlin.math.min

const val GOOD_LEAF_SIZE = 200

/** A rope sequence is a persistent sequence data structure
// that supports appending, prepending, and slicing without doing a
// full copy. It is represented as a mostly-balanced tree.
 */
abstract class RopeSequence<T> {
    // length:: number
    // The length of the rope.
    abstract val length: Int

    abstract val depth: Int

    abstract fun forEachInner(from: Int, to: Int, start: Int, f: (T, Int) -> Boolean): Boolean

    abstract fun forEachInvertedInner(from: Int, to: Int, start: Int, f: (T, Int) -> Boolean): Boolean

    abstract fun leafAppend(other: RopeSequence<T>): RopeSequence<T>?

    abstract fun leafPrepend(other: RopeSequence<T>): RopeSequence<T>?

    abstract fun sliceInner(from: Int, to: Int): RopeSequence<T>

    /** Return the content of this rope as an array. */
    abstract fun flatten(): List<T>

    abstract fun getInner(i: Int): T?

    /** (union<[T], RopeSequence<T>>) → RopeSequence<T>
     * Append an array or other rope to this one, returning a new rope.
     */
    @Suppress("ReturnCount")
    open fun append(other: RopeSequence<T>): RopeSequence<T> {
        if (other.length == 0) return this
        if (this.length == 0) return other
        if (other.length < GOOD_LEAF_SIZE) {
            val res = this.leafAppend(other)
            if (res != null) {
                return res
            }
        }
        if (this.length < GOOD_LEAF_SIZE) {
            val res = other.leafPrepend(this)
            if (res != null) {
                return res
            }
        }
        return this.appendInner(other)
    }

    open fun append(other: List<T>): RopeSequence<T> {
        if (other.isEmpty()) return this
        return append(from(other))
    }

    /** (union<[T], RopeSequence<T>>) → RopeSequence<T>
     *Prepend an array or other rope to this one, returning a new rope.
     */
    fun prepend(other: RopeSequence<T>): RopeSequence<T> {
        if (other.length == 0) return this
        return from(other).append(this)
    }

    open fun appendInner(other: RopeSequence<T>): Append<T> {
        return Append(this, other)
    }

    // :: (?number, ?number) → RopeSequence<T>
    // Create a rope repesenting a sub-sequence of this rope.
    fun slice(from: Int = 0, to: Int = this.length): RopeSequence<T> {
        if (from >= to) return empty()
        return this.sliceInner(max(0, from), min(this.length, to))
    }

    // :: (number) → T
    // Retrieve the element at the given position from this rope.
    fun get(i: Int): T? {
        if (i < 0 || i >= this.length) return null
        return this.getInner(i)
    }

    // :: ((element: T, index: number) → ?bool, ?number, ?number)
    // Call the given function for each element between the given
    // indices. This tends to be more efficient than looping over the
    // indices and calling `get`, because it doesn't have to descend the
    // tree for every element.
    fun forEach(from: Int = 0, to: Int = this.length, f: (T, Int) -> Boolean) {
        if (from <= to) {
            this.forEachInner(from, to, 0, f)
        } else {
            this.forEachInvertedInner(from, to, 0, f)
        }
    }

    // :: ((element: T, index: number) → U, ?number, ?number) → [U]
    // Map the given functions over the elements of the rope, producing
    // a flat array.
    fun <U> map(from: Int = 0, to: Int = this.length, f: (T, Int) -> U): List<U> {
        return buildList {
            forEach(
                from,
                to
            ) { elt, i ->
                add(f(elt, i))
            }
        }
    }

    companion object {
        // :: (?union<[T], RopeSequence<T>>) → RopeSequence<T>
        // Create a rope representing the given array, or return the rope
        // itself if a rope was given.
        fun <T> from(values: List<T>?): RopeSequence<T> {
            return if (values.isNullOrEmpty()) empty() else Leaf(values)
        }

        fun <T> from(values: RopeSequence<T>): RopeSequence<T> {
            return values
        }

        // :: RopeSequence
        // The empty rope sequence.
        private val empty = Leaf(emptyList<Unit>())

        @Suppress("UNCHECKED_CAST")
        fun <T> empty(): RopeSequence<T> = empty as RopeSequence<T>
    }
}

